package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 错误写法
 *
 * @author tzp
 * @since 2020/9/21
 */
public class LC1039_1 implements DynamicProblem {
    public int minScoreTriangulation(int[] A) {
        if (A == null || A.length < 3) return 0;
        if (A.length == 3) return A[0] * A[1] * A[2];

        int[][] state = new int[A.length][A.length + 1];
        for (int step = 2; step <= A.length; step++) {//从三边形开始
            for (int start = 0; start < A.length; start++) {//第一个点
                int second1 = start + 1 >= A.length ? start + 1 - A.length : start + 1;
                int second2 = start + step - 1 >= A.length ? start + step - 1 - A.length : start + step - 1;
                int third = start + step >= A.length ? start + step - A.length : start + step;
                if (step == 2) {
                    state[start][step] = A[start] * A[second1] * A[third];
                } else {
                    int s1 = state[start][step - 1] + A[start] * A[second2] * A[third];
                    int s2 = state[second1][step - 1] + A[start] * A[second1] * A[third];
                    state[start][step] = Math.min(s1, s2);
                    //错误点: f(0,5)并不是简单等于 f(0,4)+x  vs f(1,4)+x的最小值
                    // 而是需要第三层循环.
                    //需要固定的不是0,4或1,4的连续点, 是按住0和5, 让中间的点进行移动
                    //参考https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/solution/qu-jian-dong-tai-gui-hua-4ms-by-njyang-yang-yang/
                }
            }
        }
        return state[0][A.length];
    }

    public static void main(String[] args) {
        System.out.println(new LC1039_1()
                .minScoreTriangulation(new int[]{1, 3, 1, 4, 1, 5}));
    }
}
